from Chromosome import Chromosome
import random
import numpy as NP
import utility.utility as UTL
import copy

class Population(object):
	'''
	La classe Population descrive una popolazione di individui (soluzioni), rappresentati da cromosomi
	Al costruttore vengono passati parametri quali la dimensione della popolazione (il numero di individui da cui e' composta),
	i punti da clusterizzare e il numero di centroidi da usare (questi ultimi due sono parametri specifici per il caso che si sta trattando)
	'''
	
	def __init__(self, size, Patterns, nCentr):
		'''
		Metodo che inizializza casualmente i cromosomi
		(scegliendo i centroidi a caso dai dati per ciascun cromosoma)
		TODO da testare!
		'''
		self._size = size
		self._patterns = Patterns
		
		### Inizializzo la proprieta' _chromosomes come lista vuota
		self._chromosomes = []
		
		### Ricavo il numero di dimensioni dalla lunghezza del primo vettore
		self._nDim = len(Patterns[0])
		self._nCentr = nCentr
		
	def initRandomChromosomes(self):
		'''
		Inizializza casualmente i cromosomi, scegliendo i centroidi a caso dalla popolazione
		per ciascun cromosoma
		'''
		D = self.getNDimensions()
		K = self.getNCentroids()
		
		patterns = self.getPatterns()
		
		for s in range(self.getSize()):
			### Creo un nuovo cromosoma (vuoto)
			c = Chromosome(D, K)
			for i in range(K):
				### Creo un nuovo centroide scegliendolo a caso dai punti
				List = random.sample(xrange(self.getNPatterns()-1),1)
				idx = List[0]
				centroid = patterns[idx].clone()
				
				## Aggiungo l'i-esimo centroide al cromosoma
				c.setCentroid(i, centroid)
				
			### Aggiungo il cromosoma alla popolazione
			self.addChromosome(c)

	def getPatterns(self):
		'''
		Restituisce la lista dei patterns (punti) da clusterizzare
		'''
		return self._patterns
		
	def getSortedFitnessList(self):
		'''
		Restituisce una lista in cui l'i-esimo elemento indica l'indice del cromosoma nel posto i-esimo
		ordinato secondo valori CRESCENTI di fitness.
		La lista [ 13, 25, ..., 7] ad esempio indica che l'individuo avente fitness minore (il peggior individuo della popolazione)
		si trova al tredicesimo posto nella lista dei cromosomi, il secondo peggiore al posto 25. L'individuo migliore 
		si trova al settimo posto.
		Viene usato l'algoritmo d'ordinamento Insertion sort, dal momento che la lista e' piccola
		TODO fatto, da testare
		'''
		### inizio una lista contenente un numero di elementi pari al numero di cromosomi
		sorted = range(self.getSize())
		### inizializzo gli elementi col valore None
		for i in range(self.getSize()):
			sorted[i] = None
		
		chromosomes = self.getChromosomes()
		
		for i in range(self.getSize()):
			f = chromosomes[i].getFitness()
			index = 0
			for j in range(self.getSize()):
				if chromosomes[j].getFitness() < f:
					index += 1
					
			stop = False
			while(stop == False):
				if (sorted[index] == None):
					sorted[index] = i
					stop = True
				else:
					index += 1
			
		return sorted
				
	def select(self):
		'''
		Seleziona un cromosoma in base alla fitness
		'''
		chromosomes = self.getChromosomes()
		
		threshold = random.random() * self._fitness_sum
		i = 0
		while(i <= self.getSize()):
			if threshold < self._fitness_wheel[i]:
				break
			i += 1
			
		index = self._sorted_fitness_list[i]
		
		### dovrebbe clonare il cromosoma
		return copy.deepcopy(chromosomes[index])
		
	def crossover(self, c1, c2):
		'''
		effettua il crossover tra i due cromosomi c1 e c2
		'''
		### Il numero di alleli di cui e' composto il cromosoma
		DK = self.getNDimensions() * self.getNCentroids()
		
		crossover_point = random.randint(1, DK - 1)
		
		for k in range(crossover_point, DK):
			tmp = c1._alleles[k]
			c1._alleles[k] = c2._alleles[k]
			c2._alleles[k] = tmp
		
	def getNextGeneration(self, pcross, pmut):
		'''
		Restituisce la nuova popolazione
		TODO da fare!!
		'''
		N_selected = 0
		
		newpop = Population(self.getSize(), self.getPatterns(), self.getNCentroids())
		newpop._dataset_min = self._dataset_min
		newpop._dataset_max = self._dataset_max
		
		while(N_selected < self.getSize()):
			c1 = self.select()
			c2 = self.select()
			
			if (UTL.flip(pmut)):
				### Muto il primo cromosoma con probabilita' pmut
				c1.mutate(self.getMinMetric(), self.getMaxMetric(), self._dataset_min, self._dataset_max)
				
			if (UTL.flip(pmut)):
				### Muto il secondo cromosoma con probabilita' pmut
				c2.mutate(self.getMinMetric(), self.getMaxMetric(), self._dataset_min, self._dataset_max)
			
			if (UTL.flip(pcross)):
				self.crossover(c1,c2)
				
			newpop.addChromosome(c1);
			newpop.addChromosome(c2);
			
			N_selected += 2
			
		return newpop
		
	def getNCentroids(self):
		'''
		Ritorna il numero di centroidi scelto
		'''
		return self._nCentr
		
	def getNPatterns(self):
		'''
		Restituisce il numero di punti (pattern) disponibili
		'''
		return len(self.getPatterns())
		
	def getSize(self):
		'''
		Restituisce il numero di individui presenti nella popolazione
		'''
		return self._size
		
	def metricDivision(self):
		'''
		Divide ed associa i punti ai centroidi piu' vicini
		'''
		
		chromosomes = self.getChromosomes()
		
		### 1- bisogna calcolare il voronoi set
		### c'e' un voronoi set per ogni cromosoma
		### quindi una matrice K x D per ogni cromosoma j
		### matrice di appartenenza del d-esimo punto al k-esimo centroide 
		nPat = self.getNPatterns()
		patterns = self.getPatterns()
		
		### prima mi calcolo le distanze dai centroidi.					
		MATR = range(self._size) 
		for j in range(self._size):
			#~ print "---"
			MATR[j] = NP.zeros((self._nCentr,nPat))
			for k in range(nPat):
				for i in range(self._nCentr):
					MATR[j][i][k] = UTL.normaN(self._nDim,patterns[k],chromosomes[j].getCentroid(i))
					
		### ora che ho la matrice delle distanze 
		### Suddivido i punti associandoli con il nodo piu' vicino a loro
		### cerca tra i centroidi quello che ha la minor distanza dal punto. 		
		
		for j in range(self._size):
			chromosomes[j].p2c_reset()
			for k in range(nPat):
				distance = []
				for i in range(self._nCentr): 
					distance.append(MATR[j][i][k])
				minDist = min(distance)
				minIndx = distance.index(minDist)
				chromosomes[j].p2c[minIndx].append(k)

		### DEBUG stampa della divisione: 		
		#~ for j in range(self._size):
			#~ print "--"
			#~ for i in range(self._nCentr):
				#~ print chromosomes[j].p2c[i]
				
	def prepareForSelection(self):
		self._sorted_fitness_list = self.getSortedFitnessList()
		
		sorted_fitness_wheel = []
		sorted_fitness_sum = 0
		
		### P_i = ai + b
		a = 2
		b = 2
		
		for i in range(self.getSize()):
			v = a*i + b
			sorted_fitness_sum += v
			sorted_fitness_wheel.append(sorted_fitness_sum)
			
		self._fitness_sum = sorted_fitness_sum
		self._fitness_wheel = sorted_fitness_wheel
		
	def clusterize(self):
		'''
		Effettua la clusterizzazione per ogni cromosoma
		'''	
		###------ ora Aggiorniamo le pos dei cluster -----------------
		###------------------- K-Mean --------------------------------
		
		chromosomes = self.getChromosomes()
		patterns = self.getPatterns()
		
		### 1- Devo contare e dividere i punti associati ai cluster
		### NOTA: Centr contiene gli indici dei punti selezionati
		centr = range(self._size)
		nCentr = range(self._size)
		
		for j in range(self._size):
			centr[j] = range(self._nCentr)
			nCentr[j] = NP.zeros(self._nCentr)
			for i in range(self._nCentr):
				centr[j][i] =[]
		
		for j in range(self._size):
			for i in range(self._nCentr):
				centr[j][i].append(chromosomes[j].p2c[i])
				nCentr[j][i] = len(chromosomes[j].p2c[i])
		### --- DEBUG --------		
				#~ print centr[j][i]
				#~ print nCentr[j][i]
			#~ print sum(nCentr[j])
		
		### 2- Avvicino i centroidi al baricentro dei punti -----
		for j in range(self._size):
			for i in range(self._nCentr):
				 
				cNew = UTL.K_Means(patterns,centr[j][i],nCentr[j][i],self._nDim)
				
				chromosomes[j].setCentroid(i,cNew)  
							
		### -------------------------------------------------------
		
			
	def computeMetric(self):
		'''
		Calcola la metric per ciacun cromosoma
		Passa tutti i pattern come argomento ogni volta
		Tiene conto dei valori massimo e minimo della metric
		TODO valutare se regge nel caso dei dati di leukemia
		'''
		Max = None
		Min = None
		for c in self.getChromosomes():
			m = c.computeMetric(self.getPatterns())
			
			### Aggiorno il valore della metrica max
			if (Max == None or m > Max):
				Max = m
				
			### Aggiorno il valore della metrica min
			if (Min == None or m < Max):
				Min = m
				
		self._metric_MAX = Max
		self._metric_MIN = Min

	def getMaxMetric(self):
		'''
		Restituisce il valore massimo della metrica trovato
		'''		
		return self._metric_MAX

	def getDatasetMin(self, i):
		'''
		Restituisce il valore minimo del dataset lungo la dimensione i-esima
		'''
		return self._dataset_min[i]

	def getDatasetMax(self, i):
		'''
		Restituisce il valore minimo del dataset lungo la dimensione i-esima
		'''
		return self._dataset_max[i]

	def getMinMetric(self):
		'''
		Restituisce il valore minimo della metrica trovato
		'''		
		return self._metric_MIN

	def getNDimensions(self):
		'''
		Restituisce il numero di dimensioni del problema
		'''
		return self._nDim


	def getChromosomes(self):
		return self._chromosomes
		
	def addChromosome(self, c):
		self._chromosomes.append(c)
